In order to provide for rapid and orderly vehicle movement while at all times respecting the overall safety requirement, the railroad industry has evolved a control and communication system. The control problem can be analyzed in terms of sensing real time conditions in a region of the right of way (present vehicle position, direction of motion, and condition of equipment, such as switches, signals, etc.) and based on a set of pre-determined constraints imposed by the layout of the physical plant, determining what changes in equipment condition (e.g. switch position, signal condition, etc.) can be safely made to allow a vehicle to progress in its intended direction of motion. Once these decisions have been made, appropriate control signals are formulated and communicated to the actual physical plant to effect the desired changes.
Although safety is considered at every stage of information and communication processing, the railroad industry's perception and practice has been that satisfying the safety requirement at every stage in the process is unnecessary and unduly complicates the equipment. Accordingly, in practice it is only the field equipment, which translates commands into physical manifestations (throw switch, clear signal), which is designed to meet vital or fail-safe characteristics. At earlier stages in the information and communication processing, while safety is always considered, failures in equipment employed in this earlier stage of processing need not exhibit fail-safe or vital qualities. Rather, the vital or fail-safe characteristic is imposed at the very end of the control chain, e.g. at the signals and switches themselves. This has allowed the railroad industry to modernize the majority of their plant by the use, for example, of solid state circuits and digital processing without necessarily requiring that this modernized equipment exhibit vital qualities.
Nevertheless, imposition of vital design results in a vast quantity of expensive, relatively slow, bulky equipment. There is naturally a desire to eliminate these deleterious characteristics.
At the same time, the decrease in cost for digital processing equipment (e.g. the ubiquitous computer on a chip) has generated a strong desire to employ this very capable, space economical, power economical, decision making component. For a host of reasons, it has been impractical to require that the design of these microprocessors follow the vital design techniques evolved in the railroad industry over the last 100 years. Accordingly, the industry has been searching for some technique (particularly software) which could be used to transform the admittedly non-vital microprocessor into a vital system.
Solution to this problem would result in numerous advantages to the railroad industry. It would simultaneously allow the application of cheap, fast, space saving, power saving and very capable devices for replacing the bulky, slow, electromechnical vital devices which had been employed in the past.
Although control of a railroad or a portion thereof requires the solution of many different control problems, all these different problems can be generalized into a single set of characteristics. The requirements are:
1. Sensing inputs in real time (the majority of the inputs are digital in nature, and to the extent that there are any which are not digital in nature, they can be transformed into digital inputs); PA1 2. Deriving from these real time inputs a set of real time outputs for the control of different components in the railroad plant; where PA1 3. The relation between these inputs and outputs is defined by one or more logic equations which can be rigorously defined in advance. PA1 A. Providing two identical digital processors each executing an identical program and providing that the processors execute their identical program simultaneously in time by providing for synchronization therebetween, and finally providing some means for comparing the results produced by each of these processors (and in some instances, internal intermediate results as well); PA1 B. Providing two different digital processors solving the same problem in two different fashions (two different programs). In this case there is no need for synchronization since the differences in processor and program characteristics necessarily result in differences in internal machine states; checking in this solution is only at the level of ultimate outputs. PA1 (a) The factor to be "added" is added, modulo 2, to the shift register. This is an independent operation at each bit position, the bit in any shift register position is added, modulo 2 to the corresponding bit of the factor. Addition modulo 2 obeys these rules, 1+0 =1; 0+1=1; 1+1=0; and PA1 (b) This shift register is again stepped a number of times A (again one bit shift per step). PA1 data sensing apparatus for performing sensing of essentially binary data in a vital fashion, including: PA1 a data bus with plural conductors, PA1 a memory maintaining a table of multi-bit data units for outputting to said data bus one or more of said multi-bit data units in bit parallel, unit serial order, PA1 a group drive circuit connecting different conductors of said data bus to different sense circuits, PA1 a plurality of sense circuits, one for each different input device, each with two inputs and an output, a first input of each sense circuit coupled to an input device, a second input of each sense circuit connected to said group drive circuit, said output coupled to a conductor of said data bus associated with said second input of said sense circuit, PA1 transposition means coupled to said data bus and responsive to signals placed thereon by said sense circuits for temporarily storing a sequence of received multi-bit data units equal in length to the multi-bit data units serially output by said memory means and for transposing the received multi-bit data units from bit parallel unit serial order to unit parallel, bit serial order. PA1 (a) assigning each of said inputs first and second groups of binary digits, one of said groups representing a true state of the corresponding input and the other of said groups representing the false state of said input, said first and second groups being different from each other and different from all other groups of binary digits assigned to all other inputs, PA1 (b) assigning each of said outputs first and second groups of binary digits, one of said groups representing the true state of the corresponding output and the other group representing the false state of the corresponding output, said first and second groups being different from each other, different from all other binary groups assigned to all other outputs, and different from all binary groups assigned to all said inputs, such that a particular binary group not only represents the condition of the corresponding output but also serves to identify the corresponding output, PA1 (c) providing a set of equations relating each output to one or more of said inputs and none, one or more of said outputs, PA1 (d) testing said inputs and writing a group of binary digits, one for each input, selected from the groups assigned to said input in dependence on the result of testing of the input, PA1 (e) computing values for each of said outputs in accordance with said equations and said written groups of binary digits, PA1 (f) controlling said outputs in accordance with said computed value for the corresponding output, PA1 (a) providing a feedback shift register, with plural stages, arranged to provide maximal length sequences, PA1 (b) preconditioning said feedback shift register by controlling each stage thereof to attain a condition identical to a corresponding bit of a predetermined bit pattern, PA1 (c) shifting one of said input multi-bit binary values into said feedback shift register, and PA1 (d) repeating said step (c) for each other of said input multi-bit binary values.
It would be inadequate for such a device to be merely capable of vitally solving the equations referred to in item 3, because the vital characteristic has got to cover not only the solution of logic equations, but sensing of the inputs and checking that the outputs presented to the railroad plant are in fact those outputs which have been derived by the solution of the logic equations.
Others in the field have attempted solutions to this problem, with differing success; some of these solutions have applied traditional EDP techniques. These solutions include:
An entirely different solution has been proposed for certain aspects of the problem related to communications. See, for example, Sibley U.S. patent application Ser. No. 273,299 filed June 15, 1981, entitled "Vital Communication System for Transmitting Multiple Messages", now U.S. Pat. No. 4,471,486. In this solution, it appears externally that there is only a single processor solving a single program; internally, however, in a time multiplexed fashion, the single program includes at least some diversity in that at least critical portions of the solution produce check words. The result of the single processor is provided in two forms, the first form is the outputs destined for the real world, and the second form is a series of check words which by their number and content perform a telltale function indicating the particular logic path followed by the program in the solution of the logic problem. Associated with the first processor (or vital processor) is a second processor (a vital driver); note that this is different from the solutions A and B noted above because the second processor is not at all concerned with the solution of any problem related to the real world environment. Rather, the purpose of the second processor is merely to review the number and content of the check words produced by the first processor. Only if the second processor indicates that the check words, by their number and content, verify the accurate execution by the first processor, will the real world outputs of the first processor be allowed to become effective. In order to close the loop, this solution has employed one or more techniques to verify that the input function has been performed vitally (that a closed contact, if present, is actually sensed, and that the representation within the first processor of this closed contact is indeed a representation of a closed contact) as well as checking that the potential outputs which the first processor indicates it will make effective if allowed, are in fact those outputs which flow from the solution of the logic equations by the first processor, e.g. is the output really dictated by the internal processes of the first processor, or does the output merely reflect a failed component?
Since the input information is essentially digital, as is the output, a very real difficulty is the need to verify that the single bit representation of this input which is being sensed or the output which is being checked, is appropriate; specifically that the input representation sensed by the machine, or the output representation being checked by the machine, has not been masked by a failure. Although all failure mechanisms have not been rigorously defined, two of the failure mechanisms which are well known are the "stuck bit" (where a bit is stuck in one of its two conditions) and the shorted terminal (where one terminal is shorted to another). Prior examples of techniques for overcoming these failure modes are illustrated in Sibley U.S. Pat. No. 4,365,164.
Another difficulty which must be overcome is a byproduct of the presence within typical microprocessor systems of memory. The memory function presents at least two problems, data stored in the memory is going to be used in one or more intermediate processes, and even assuming that the data which had been stored in the memory was correct at some time in the past, how do we know that data is still valid when it is being used? Furthermore, and also assuming that the data which is stored in the memory was and is correct, how do we know that the data we have extracted from memory is the data which we desire, and is not the result of some failure in an addressing mechanism?
One solution to the second problem is described in co-pending U.S. patent application Ser. No. 241,819, filed Mar. 9, 1981, now U.S. Pat. No. 4,485,435, and assigned to the assignee of this application. This technique requires that once data has been used (or the last time it has been used) the data is destroyed. To ensure that data destruction has actually been carried out, each process which relies on the presence of current data includes an initialization routine solely for the purpose of checking that the data previously residue in the memory location, area or region, has in fact been destroyed. This initialization process produces one or more check words. The check words so produced are actuall shipped over to the vital driver (the other, or checking processor) and unless the check words are correct (proving that old data had previously been destroyed and the results being checked are truly the result of current data) the checking processor will not produce the correct result which will not allow application of the vital processors' outputs. The whole system is arranged so that disallowance of outputs produces an entirely safe condition (albeit not necessarily the most efficient condition--all signals to stop). Furthermore, the check word using technique is arranged such that neither the vital processor nor the vital driver has stored therein the "right" answer. The presence of the "right" answer stored somewhere in machine memory raises the possibility that the "right" answer will be derived from memory and not necessarily reflect the appropriate checks. Therefore, in this and all other uses of check words for verification techniques, we must assure that the "right" answer is not available to the machine except by the intended processing.